Currently, there is great interest in soft-input/soft-output (SISO) algorithms due to the outstanding performance of iterative data detection. Like the Viterbi algorithm (VA), the SISO algorithm is derived for an embedded system that can be modeled as a finite state machine (FSM). However, instead of making hard decisions as does the VA, the SISO algorithm generates soft decisions, i.e., reliability measures, for the investigated data. A hard decision can be readily obtained by thresholding the soft information. The key notion carried with the soft information, also its main advantage over a hard decision, is that the soft information can be refined by some way (e.g., through iteration) to make a later hard decision more reliable. Thus, the SISO algorithm is especially well-suited for iterative data detection. Because of this advantage, SISO algorithms have been widely used in various application, such as decoding of (both serial and parallel) Turbo codes and other codes, near-capacity multi-user detection, near-optimal two-dimensional data detection, and the detection of TCM signals in fading channels.
The biggest obstacle facing a practical implementation of the SISO algorithm is probably its complexity. The complexity of a SISO algorithm grows exponentially with the memory length of the FSM, e.g., the number of taps in an inter-symbol interference (ISI) channel or the constraint length of a convolutional code. It is not difficult to imagine how the complexity of such an algorithm can quickly overwhelm even the most advanced signal processing hardware and software. For a fixed-interval minimum sequence metric (FI-MSM) SISO algorithm, its computational complexity is approximately twice that of the VA and the number of memory units required is proportional to the product of block length and the number of states of the FSM. For instance, when the FI-MSM algorithm is applied to a 10-tap ISI channel with QPSK signaling, its complexity is dominated by the number of the states of the FSM, which is the order of the modulation scheme raised to an exponential equal the number of taps minus one (49=262,144). This relatively simple example of a transmitter and channel thus presents an implementation nightmare, as the relevant signal processing system is asked to perform SISO computations based on 262,144 possible states, a task that is practically infeasible today for most applications.
Therefore, there is a need for a method of digital information processing for producing soft outputs based on soft inputs that offers a significant reduction in computational and memory complexity from the standard SISO algorithm but is still capable of excellent performance.